﻿// 4871. 最早时刻.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

/*
https://www.acwing.com/problem/content/4874/

给定一个 n
 个点 m
 条边的不含重边和自环的无向图。

点的编号为 1∼n
，边的编号为 1∼m
。

在 t=0
 时刻，你位于 1
 号点。

你的任务是尽可能早的抵达 n
 号点。

第 i
 条边连接点 ai
 和点 bi
，通过此边需要花费的时间为 ci
。

在整个移动过程中，你只有在整数时刻才能离开某一点前往另一点。

此外，第 i
 个点有 ki
 个禁止离开时刻。

在每个点的禁止离开时刻，你无法离开该点前往其它点。

请你计算抵达 n
 号点的最早可能时刻。

输入格式
第一行包含两个整数 n,m
。

接下来 m
 行，其中第 i
 行包含三个整数 ai,bi,ci
，表示第 i
 条边连接点 ai
 和 bi
，通过此边需要花费的时间为 ci
。

接下来 n
 行，其中第 i
 行首先包含一个整数 ki
，表示第 i
 个点有 ki
 个禁止离开时刻，随后包含 ki
 个互不相同的升序排序的整数 tij
，表示所有禁止离开时刻。

输出格式
一个整数，表示抵达 n
 号点的最早可能时刻。

如果无法抵达 n
 号点，则输出 -1。

数据范围
前 4
 个测试点满足 2≤n≤4
。
所有测试点满足 2≤n≤105
，0≤m≤105
，1≤ai,bi≤n
，ai≠bi
，1≤ci≤104
，0≤ki≤105
，0≤tij<109
，所有 ki
 相加之和不超过 105
。

输入样例1：
4 6
1 2 2
1 3 3
1 4 8
2 3 4
2 4 5
3 4 3
0
1 3
2 3 4
0
输出样例1：
7
样例1解释
从点 1
 到点 4
，考虑如下三条路线：

在时刻 0
 通过第 3
 条边离开点 1
，并于时刻 8
 抵达点 4
。
在时刻 0
 通过第 2
 条边离开点 1
，并于时刻 3
 抵达点 3
，由于点 3
 在时刻 3,4
 禁止离开，所以在时刻 5
 通过第 6
 条边离开点 3
，并于时刻 8
 抵达点 4
。
在时刻 0
 通过第 1
 条边离开点 1
，并于时刻 2
 抵达点 2
，在时刻 2
 通过第 5
 条边离开点 2
，并于时刻 7
 抵达点 4
。
最佳方案为第三条路线，抵达点 4
 的最早可能时刻为 7
。

输入样例2：
3 1
1 2 3
0
1 3
0
输出样例2：
-1
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 